<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>&#x6570;&#x7EC4;&#x53BB;&#x91CD;</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-body vscode-light">
        <h1 id="数组去重">数组去重</h1>
<h1 id="1-链表去除重复的元素">1. 链表去除重复的元素</h1>
<p>情况(1) ， 每个元素最多只能出现一次  1-&gt;1-&gt;1-&gt;2-&gt;3    to  1-&gt;2-&gt;3</p>
<ul>
<li>
<ol start="83">
<li>Remove Duplicates from Sorted List</li>
</ol>
</li>
</ul>
<p>情况(2) , 只要是重复出现的元素都删掉  1-&gt;1-&gt;1-&gt;2-&gt;3   to    2-&gt;3</p>
<ul>
<li>
<ol start="82">
<li>Remove Duplicates from Sorted List II</li>
</ol>
</li>
</ul>
<p>下面是一个统一的框架来解决这2个问题</p>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removed_duplication_final</span>(<span class="hljs-params">head</span>):</span>
    <span class="hljs-string">&#x27;&#x27;&#x27;  final version, 同时能处理两种情况的
        (1) removed duplication,  1-&gt;1-&gt;1-&gt;2-&gt;3  to  1-&gt;2-&gt;3
        (2) removed duplication2,  1-&gt;1-&gt;1-&gt;2-&gt;3  to  2-&gt;3
        2 points solution

        下面的代码是针对 情况(1) 1-&gt;1-&gt;1-&gt;2-&gt;3  to  1-&gt;2-&gt;3
        加上被注释的5行，就可以处理情况(2) 1-&gt;1-&gt;1-&gt;2-&gt;3  to  2-&gt;3
    &#x27;&#x27;&#x27;</span>

    <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> head:
        <span class="hljs-keyword">return</span> <span class="hljs-literal">None</span>
    dummy = ListNode(head.val)
    dummy.next = head
    pre = dummy
    current = pre.next
    <span class="hljs-keyword">while</span> current:
        <span class="hljs-comment">#duplicated = False  # 针对 (2)  line1</span>
        <span class="hljs-keyword">while</span> current.next <span class="hljs-keyword">and</span> current.next.val == current.val:
            <span class="hljs-comment">#duplicated = True  # 针对 (2) line2</span>
            current = current.next


        <span class="hljs-comment">#if duplicated:              # 针对 (2) line3</span>
        <span class="hljs-comment">#    current = current.next  # 针对 (2) line4</span>
        <span class="hljs-comment">#    continue                # 针对 (2) line5</span>

        pre.next = current
        pre = pre.next
        current = current.next

    pre.next = <span class="hljs-literal">None</span>
    <span class="hljs-keyword">return</span> dummy.next
</div></code></pre>
<h1 id="2-数组去掉重复的元素">2. 数组去掉重复的元素</h1>
<ul>
<li>
<ol start="26">
<li>Remove Duplicates from Sorted Array</li>
</ol>
</li>
</ul>
<p>完全一样的思路, 可以解决同样的两种情况</p>
<pre><code class="language-python"><div>    <span class="hljs-string">&#x27;&#x27;&#x27;  final version, 同时能处理两种情况的
        (1) removed duplication,  1-&gt;1-&gt;1-&gt;2-&gt;3  to  1-&gt;2-&gt;3
        (2) removed duplication2,  1-&gt;1-&gt;1-&gt;2-&gt;3  to  2-&gt;3
        2 points solution

        下面的代码是针对 情况(1) [1,1,1,2,3]  to  [1,2,3]
        加上被注释的5行，就可以处理情况(2) [1,1,1,2,3]  to  [1,2,3]
    &#x27;&#x27;&#x27;</span>

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeDuplicates</span>(<span class="hljs-params">self, nums: List[int]</span>) -&gt; int:</span>
        p1 = <span class="hljs-number">-1</span>
        p2 = <span class="hljs-number">0</span>
        len_nums = len(nums)
        <span class="hljs-keyword">while</span> p2 &lt; len_nums:
            <span class="hljs-comment">#duplicate = False      # 针对 (2)  line1</span>
            <span class="hljs-keyword">while</span> p2 &lt; len_nums - <span class="hljs-number">1</span> <span class="hljs-keyword">and</span> nums[p2] == nums[p2+<span class="hljs-number">1</span>]:
                <span class="hljs-comment">#duplicate = True   # 针对 (2) line2</span>
                p2 += <span class="hljs-number">1</span>
                
            <span class="hljs-comment">#if p2 &gt; 0 and nums[p2] == nums[p2-1]:  # duplicate 变量相关的代码可以不要，用这一行来替代</span>
            <span class="hljs-comment">#if duplicate:             # 针对 (2) line3</span>
            <span class="hljs-comment">#    p2 += 1               # 针对 (2) line4</span>
            <span class="hljs-comment">#    continue              # 针对 (2) line5</span>
                
            p1 += <span class="hljs-number">1</span>
            nums[p1] = nums[p2]
            p2 += <span class="hljs-number">1</span>
            
        <span class="hljs-keyword">return</span> p1+<span class="hljs-number">1</span>
</div></code></pre>
<h1 id="3-情况3-允许每个元素最多出现2次">3. 情况3 允许每个元素最多出现2次</h1>
<ul>
<li>
<ol start="80">
<li>Remove Duplicates from Sorted Array II</li>
</ol>
</li>
</ul>
<p>我没想到的是 Remove Duplicates from Sorted Array II 不是情况 “(2) 只要是重复出现的元素都删掉”,
而是情况(3) 允许每个元素最多出现2次   [1,1,1,2,3]  to  [1,1, 2,3]</p>
<p>那么上面的框架怎么修改呢？ 仔细想想也不复杂，只要改一下判断条件即可。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeDuplicates</span>(<span class="hljs-params">self, nums: List[int]</span>) -&gt; int:</span>
        p1 = <span class="hljs-number">-1</span>
        p2 = <span class="hljs-number">0</span>
        len_nums = len(nums)
        <span class="hljs-keyword">while</span> p2 &lt; len_nums:
            <span class="hljs-keyword">while</span> p2 &lt; len_nums - <span class="hljs-number">2</span> <span class="hljs-keyword">and</span> nums[p2] == nums[p2+<span class="hljs-number">1</span>] <span class="hljs-keyword">and</span> nums[p2] == nums[p2+<span class="hljs-number">2</span>]:
                p2 += <span class="hljs-number">1</span>
                
                
            p1 += <span class="hljs-number">1</span>
            nums[p1] = nums[p2]
            p2 += <span class="hljs-number">1</span>
            
        <span class="hljs-keyword">return</span> p1+<span class="hljs-number">1</span>
</div></code></pre>
<p>由此引申出了，如果题目改成允许每个元素最多出现k次，怎么办？ 像下面这样修改判断条件即可</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeDuplicates</span>(<span class="hljs-params">self, nums: List[int]</span>) -&gt; int:</span>
        p1 = <span class="hljs-number">-1</span>
        p2 = <span class="hljs-number">0</span>
        len_nums = len(nums)
        k = <span class="hljs-number">2</span>
        <span class="hljs-keyword">while</span> p2 &lt; len_nums: 
            <span class="hljs-keyword">while</span> p2 &lt; len_nums - k:
                key = nums[p2]
                r = [t-key == <span class="hljs-number">0</span> <span class="hljs-keyword">for</span> t <span class="hljs-keyword">in</span> nums[p2+<span class="hljs-number">1</span>:p2+k+<span class="hljs-number">1</span>]]
                <span class="hljs-keyword">if</span> all(r):
                    p2 += <span class="hljs-number">1</span>
                <span class="hljs-keyword">else</span>:
                    <span class="hljs-keyword">break</span>
    
                
            p1 += <span class="hljs-number">1</span>
            nums[p1] = nums[p2]
            p2 += <span class="hljs-number">1</span>
            
        <span class="hljs-keyword">return</span> p1+<span class="hljs-number">1</span>
</div></code></pre>

    </body>
    </html>